Multi-hop wireless networks have been the subject of much study over the past few decades. Much of the original work was motivated by military applications such as battlefield communications. More recently, however, some interesting commercial applications have emerged. One example is “community wireless networks”, where a multi-hop wireless network, perhaps based on the IEEE 802.11 standard, is used to provide the “last-mile” to peoples' homes. A very different example is sensor networks where the scale and environment make a multi-hop wireless network the only feasible means of communication.
A fundamental issue in multi-hop wireless networks is that performance degrades sharply as the number of hops traversed increases. As a simple example, in a network comprising nodes with identical and omni-directional radio ranges, going from a single hop to two hops halves the throughput of a flow because wireless interference dictates that only one of the two hops can be active at a time.
The performance challenges of multi-hop networks have long been recognized and have led to much work on new and better solutions for the medium access control (MAC), routing, and transport layers of the protocol stack. However, in recent years, there has also been a focus on the fundamental question of what the capacity of a multi-hop wireless network is. The seminal paper by Gupta and Kumar (see Gupta, P., and Kumar, P. R., “The capacity of wireless networks,” IEEE Transactions on Information Theory 46, 2 (March 2000)) showed that in a network comprising of n identical nodes, each of which is communicating with another node, the throughput capacity per node is Θ(1/√n log n) assuming random node placement and communication pattern and Θ(1/√n) assuming optimal node placement and communication pattern. Subsequent work has considered alternative models and settings, such as the presence of relay nodes and mobile nodes, and locality in inter-node communication, and their results are less pessimistic.